package mid.class4;

/**
 * 并查集
 * [1,1,3,3,5,5,7,7,9,9]
 * [0,1,2,3,4,5,6,7,8,9]
 */
public class Code02_UnionFind {

    private static class UnionFind {
        public static int MAX = 1000001;

        public static int[] father = new int[MAX];

        public static void build(int n) {
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        // i 号节点，往上一直找，找到代表节点后返回
        public int find(int i) {
            if (i != father[i]) { // i不为代表值
                father[i] = find(father[i]);
            }
            return father[i];
        }

        // 代表值是否相同
        public boolean isSameSet(int x, int y) {
            return find(x) == find(y);
        }

        // 代表值 合并
        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            father[fx] = fy;
        }
    }
}


